class DynamicProgramming:
    @staticmethod
    def fibonacci(n):
        """
        斐波那契数列算法

        参数:
        n (int): 要计算的斐波那契数列的项数

        返回:
        int: 第n项的值

        实现步骤:
        1. 创建一个列表用于存储斐波那契数列的值
        2. 初始化前两项为0和1
        3. 通过动态规划的方式计算斐波那契数列的值
        4. 返回第n项的值

        """

        # 步骤 1: 创建一个列表用于存储斐波那契数列的值
        fib = [0] * (n + 1)

        # 步骤 2: 初始化前两项为0和1
        fib[0] = 0
        fib[1] = 1

        # 步骤 3: 通过动态规划的方式计算斐波那契数列的值
        for i in range(2, n + 1):
            fib[i] = fib[i - 1] + fib[i - 2]

        # 步骤 4: 返回第n项的值
        return fib[n]

    @staticmethod
    def knapsack(weights, values, capacity):
        """
        背包问题算法

        参数:
        weights (List[int]): 物品的重量列表
        values (List[int]): 物品的价值列表
        capacity (int): 背包的容量

        返回:
        int: 背包中可以放置的最大价值

        实现步骤:
        1. 创建一个二维列表用于存储子问题的最优解
        2. 初始化边界条件
        3. 通过动态规划的方式计算子问题的最优解
        4. 返回背包中可以放置的最大价值

        """

        # 步骤 1: 创建一个二维列表用于存储子问题的最优解
        n = len(weights)
        dp = [[0] * (capacity + 1) for _ in range(n + 1)]

        # 步骤 2: 初始化边界条件
        for i in range(n + 1):
            dp[i][0] = 0
        for j in range(capacity + 1):
            dp[0][j] = 0

        # 步骤 3: 通过动态规划的方式计算子问题的最优解
        for i in range(1, n + 1):
            for j in range(1, capacity + 1):
                if weights[i - 1] > j:
                    dp[i][j] = dp[i - 1][j]
                else:
                    dp[i][j] = max(dp[i - 1][j], values[i - 1] + dp[i - 1][j - weights[i - 1]])

        # 步骤 4: 返回背包中可以放置的最大价值
        return dp[n][capacity]

    @staticmethod
    def longest_increasing_subsequence(nums):
        """
        最长递增子序列算法

        参数:
        nums (List[int]): 输入的列表

        返回:
        int: 最长递增子序列的长度

        实现步骤:
        1. 创建一个列表用于存储每个元素对应的最长递增子序列长度
        2. 初始化每个元素的最长递增子序列长度为1
        3. 通过动态规划的方式计算每个元素的最长递增子序列长度
        4. 返回最长递增子序列的长度

        """

        # 步骤 1: 创建一个列表用于存储每个元素对应的最长递增子序列长度
        dp = [1] * len(nums)

        # 步骤 2: 初始化每个元素的最长递增子序列长度为1
        for i in range(len(nums)):
            dp[i] = 1

        # 步骤 3: 通过动态规划的方式计算每个元素的最长递增子序列长度
        for i in range(1, len(nums)):
            for j in range(i):
                if nums[i] > nums[j]:
                    dp[i] = max(dp[i], dp[j] + 1)

        # 步骤 4: 返回最长递增子序列的长度
        return max(dp)

    @staticmethod
    def max_subarray_sum(nums):
        """
        最大子数组和算法

        参数:
        nums (List[int]): 输入的列表

        返回:
        int: 最大子数组的和

        实现步骤:
        1. 定义两个变量用于存储当前的最大和和全局的最大和
        2. 遍历数组，更新当前的最大和
        3. 更新全局的最大和
        4. 返回全局的最大和

        """

        # 步骤 1: 定义两个变量用于存储当前的最大和和全局的最大和
        cur_max = nums[0]
        global_max = nums[0]

        # 步骤 2: 遍历数组，更新当前的最大和
        for i in range(1, len(nums)):
            cur_max = max(nums[i], cur_max + nums[i])

            # 步骤 3: 更新全局的最大和
            global_max = max(global_max, cur_max)

        # 步骤 4: 返回全局的最大和
        return global_max

    @staticmethod
    def longest_common_subsequence(s1, s2):
        """
        最长公共子序列算法（Longest Common Subsequence Algorithm）

        参数：
        s1 (str): 字符串1。
        s2 (str): 字符串2。

        返回：
        Tuple[int, str]: 最长公共子序列的长度和最长公共子序列本身。

        实现步骤：
        1. 创建一个二维数组dp，dp[i][j]表示s1的前i个字符与s2的前j个字符的最长公共子序列的长度。
        2. 初始化dp数组，将所有元素设置为0。
        3. 遍历字符串s1和s2，根据状态转移方程计算dp[i][j]：
        - 如果s1[i - 1] == s2[j - 1]（当前字符相等），则最长公共子序列长度加1：
            dp[i][j] = dp[i - 1][j - 1] + 1
        - 否则，取两个字符串去掉最后一个字符后的最长公共子序列长度的较大值：
            dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])
        4. 根据dp数组构造最长公共子序列。
        5. 返回最长公共子序列的长度和最长公共子序列本身，即dp[m][n]和构造的子序列。

        """

        m, n = len(s1), len(s2)
        dp = [[0] * (n + 1) for _ in range(m + 1)]

        # 3. 遍历字符串s1和s2，计算dp[i][j]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                if s1[i - 1] == s2[j - 1]:
                    # 当前字符相等，最长公共子序列长度加1
                    dp[i][j] = dp[i - 1][j - 1] + 1
                else:
                    # 当前字符不相等，取较大值
                    dp[i][j] = max(dp[i - 1][j], dp[i][j - 1])

        # 4. 根据dp数组构造最长公共子序列
        lcs_length = dp[m][n]
        lcs = []
        i, j = m, n
        while i > 0 and j > 0:
            if s1[i - 1] == s2[j - 1]:
                lcs.append(s1[i - 1])
                i -= 1
                j -= 1
            elif dp[i - 1][j] > dp[i][j - 1]:
                i -= 1
            else:
                j -= 1
        lcs.reverse()

        # 5. 返回最长公共子序列的长度和最长公共子序列本身
        return lcs_length, ''.join(lcs)




    @staticmethod
    def floyd_warshall(graph):
        """
        最短路径算法（Floyd-Warshall Algorithm）

        参数：
        graph (list): 图的邻接矩阵表示。

        返回：
        list: 所有节点之间的最短路径长度矩阵。

        实现思路：
        1. 创建一个二维数组dp，dp[i][j]表示节点i到节点j的最短路径长度。
        2. 初始化dp数组为图的邻接矩阵。
        3. 遍历中间节点，遍历节点对(i, j)，更新dp[i][j]：
           - 如果dp[i][k] + dp[k][j] < dp[i][j]，则更新dp[i][j]的值为更小的路径长度。
        4. 返回所有节点之间的最短路径长度矩阵。

        """

        n = len(graph)
        dp = [row[:] for row in graph]

        # 3. 遍历中间节点
        for k in range(n):
            # 4. 遍历节点对(i, j)，更新dp[i][j]
            for i in range(n):
                for j in range(n):
                    if dp[i][k] + dp[k][j] < dp[i][j]:
                        dp[i][j] = dp[i][k] + dp[k][j]

        # 5. 返回所有节点之间的最短路径长度矩阵
        return dp


if __name__ == '__main__':
    # 斐波那契数列算法
    n = 10
    fib_result = DynamicProgramming.fibonacci(n)
    print("斐波那契数列第{}项的值: {}".format(n, fib_result))
    # 斐波那契数列第10项的值: 55
    
    # 背包问题算法
    weights = [2, 3, 4, 5]
    values = [3, 4, 5, 6]
    capacity = 5
    knapsack_result = DynamicProgramming.knapsack(weights, values, capacity)
    print("背包中可以放置的最大价值: {}".format(knapsack_result))
    # 背包中可以放置的最大价值: 7

    # 最长递增子序列算法
    nums = [10, 9, 2, 5, 3, 7, 101, 18]
    lis_result = DynamicProgramming.longest_increasing_subsequence(nums)
    print("最长递增子序列的长度: {}".format(lis_result))
    # 最长递增子序列的长度: 4 

    # 最大子数组和算法
    nums = [-2, 1, -3, 4, -1, 2, 1, -5, 4]
    max_subarray_sum_result = DynamicProgramming.max_subarray_sum(nums)
    print("最大子数组的和: {}".format(max_subarray_sum_result))
    # 最大子数组的和: 6

    # 示例调用最长公共子序列算法
    s1 = "ABCBDAB"
    s2 = "BDCAB"
    lcs_length = DynamicProgramming.longest_common_subsequence(s1, s2)
    print("最长公共子序列的长度:", lcs_length)
    """
    示例输出结果:
    最长公共子序列的长度: 4
    """

    # 示例调用最短路径算法(Floyd-Warshall算法)
    graph = [
        [0, 2, float('inf'), 1],
        [float('inf'), 0, 2, float('inf')],
        [3, float('inf'), 0, float('inf')],
        [float('inf'), 4, 2, 0]
    ]
    shortest_paths = DynamicProgramming.floyd_warshall(graph)
    print("所有节点之间的最短路径长度矩阵:")
    for i in range(len(shortest_paths)):
        print(shortest_paths[i])
    """
    示例输出结果:
    所有节点之间的最短路径长度矩阵:
    [0, 2, 3, 1]
    [5, 0, 2, 6]
    [3, 5, 0, 4]
    [5, 4, 2, 0]
    """
